package dynamicStudy;

public class DynamicStudy06 {

    /**
     * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
     *
     * '.' 匹配任意单个字符
     * '*' 匹配零个或多个前面的那一个元素
     * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
     *
     * 首先：确定最后一步和子问题，找出状态，状态为是否可以匹配，最后一步
     *
     * 总结：学会逆向思维，先找到最后一步，然后确定最后一步对应的子问题，然后就可以确定转换方程。
     * 学会列举出所有到达最后一步的情况
     * @param args
     */
    public static void main(String[] args) {
        boolean[][] a = new boolean[3][3];
        for (int i = 0; i < 3; i++){
            for (int j = 0; j < 3; j++){
                System.out.print(a[i][j]);
            }
            System.out.println();
        }
    }

    public static boolean isMatch(String s, String p){
        int m = s.length();
        int n = p.length();
        //开辟二维数组，存放匹配状态
        boolean[][] dp = new boolean[m + 1][n + 1];

        //初始化，确定边界
        dp[0][0] = true;

        //循环体
        for (int i = 0; i < m + 1; i++){
            //由于boolean类型的数组的默认值为false，所以第一列默认初始化为false
            for (int j = 1; j < n + 1; j++){
                if (p.charAt(j-1) == '*'){
                    //直接匹配0次
                    dp[i][j] = dp[i][j-2];
                    //如果匹配成功，选择匹配一次或者一次不匹配，因为要尽量让他满足，默认为不满足的情况
                    if (matches(s, p, i, j - 1)){
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)){
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }
        return dp[m][n];
    }

    //判断字符是否能够匹配
    public static boolean matches(String s, String p, int i, int j){
        if (i == 0){
            return false;
        }
        if (p.charAt(j - 1) == '.'){
            return true;
        }
        return s.charAt(i - 1) == s.charAt(j - 1);
    }
}
